import math
from tkinter import Tk
from GraphicsInterface import GraphicsInterface
from Node import Node

class Graph :
    nodes = []
    links = []

    def readNodes(self, filename) :
        self.nodes.clear()
        fin = open(filename)
        for dataline in fin.readlines() :            
            data = dataline.split(';')
            if data[0] != "Name" and len(data) == 3 :
                self.nodes.append(Node(data[0].strip(), int(data[1]), int(data[2][:-1])))
        fin.close()
        del fin
        del dataline
        del data

    def readLinks(self, filename) :
        self.links.clear()
        fin = open(filename)
        for dataline in fin.readlines() :
            data = dataline.split(';')
            if data[0] != "from" and len(data) == 2 :
                #self.links.append(Link(data[0].strip(), data[1][:-1].strip()))
                start = self.getNode(data[0].strip())
                end = self.getNode(data[1][:-1].strip())
                if end not in start.children :
                    start.children.append(end)
                if start not in end.children :
                    end.children.append(start)
        fin.close()
        del fin
        del dataline
        del data

    def printNodes(self) :
        for node in self.nodes :
            node.print()
        del node

    def printLinks(self) :
        for link in self.links :
            link.print()
        del link

    def getNodeDist(self, start, end) :
        fromX, fromY = self.getCoords(start)
        toX, toY = self.getCoords(end)
        #print("Distance from", link.start, "to", link.end, "is", math.sqrt(math.pow(toX - fromX, 2) + math.pow(toY - fromY, 2))) #debugging
        return math.sqrt(math.pow(toX - fromX, 2) + math.pow(toY - fromY, 2))

    def getCoords(self, name) :
        for node in self.nodes :
            if node.name == name :
                return (node.x, node.y)

    def getNode(self, name) :
        for node in self.nodes :
            if node.name == name :
                return node

    def drawMap(self) :            
        root = Tk()
        graphics = GraphicsInterface(root)
        root.geometry("1280x720+300+300")       
        graphics.drawMap(self.nodes)

    def IDDFSearch(self, start, goal) :
        expanded = 0
        for d in range(1,10) :
            frontier = []
            frontier.append([self.getNode(start)])
            while len(frontier) > 0 :
                path = frontier.pop()
                if path[-1].name == goal :
                    print("\nExpanded ", expanded, " nodes to find path", sep="")
                    return path
                if len(path) < d :
                    expanded += 1
                    for child in path[-1].children :
                        if child not in path :
                            frontier.append(path + [child])
                    del child


    def BFRSearch(self, start, goal) :
        expanded = 0
        frontier = []
        frontier.append([self.getNode(start)])
        while len(frontier) > 0 :
            path = frontier.pop(self.BFRHeuristicSelection(frontier, goal))
            if path[-1].name == goal :
                print("\nExpanded ", expanded, " nodes to find path", sep="")
                return path   
            expanded += 1 
            for child in path[-1].children :
                if child not in path :
                    frontier.append(path + [child])                            
            del child

    def BFRHeuristicSelection(self, frontier, goal) :
        minIndex = 0
        minDist = self.getNodeDist(frontier[0][-1].name, goal)
        for i in range(1, len(frontier)) :
            nodeDist = self.getNodeDist(frontier[i][-1].name, goal)
            if nodeDist < minDist :
                minIndex = i
                minDist = nodeDist
        return minIndex

    def AStarSearch(self, start, goal) :
        expanded = 0
        frontier = []
        explored = []
        traveledDist = {}
        parentNode = {}
        frontier.append(self.getNode(start))
        traveledDist[start] = 0
        while len(frontier) > 0 :
            node = frontier.pop(self.AStarHeuristicSelection(frontier, traveledDist, goal))
            explored.append(node)
            if node.name == goal :
                print("\nExpanded ", expanded, " nodes to find path", sep="")
                return self.AStarRebuildPath(parentNode, start, goal)
            expanded += 1
            for child in node.children :
                childDist = traveledDist[node.name] + self.getNodeDist(node.name, child.name)
                if child in explored :
                    if childDist < traveledDist[child.name] :
                        frontier.append(explored.pop(self.getNode(child.name)))
                        traveledDist[child.name] = childDist
                        parentNode[child.name] = node.name
                elif child in frontier :
                    if childDist < traveledDist[child.name] :
                        traveledDist[child.name] = childDist
                        parentNode[child.name] = node.name
                else :
                    frontier.append(child)  
                    parentNode[child.name] = node.name                    
                    traveledDist[child.name] = childDist 
            del child

    def AStarHeuristicSelection(self, frontier, traveled, goal) :
        minIndex = 0
        minScore = self.getNodeDist(frontier[0].name, goal) + traveled[frontier[0].name]
        for i in range(1, len(frontier)) :
            nodeScore = math.floor(self.getNodeDist(frontier[i].name, goal) + traveled[frontier[i].name])
            if nodeScore < minScore :
                minIndex = i
                minScore = nodeScore
        return minIndex

    def AStarRebuildPath(self, parentNode, start, goal) :
        list= []
        currentNode = self.getNode(goal)
        while currentNode.name != start :            
            list.append(currentNode)
            currentNode = self.getNode(parentNode[currentNode.name])
        list.append(currentNode)
        list.reverse()
        return list
